package com.yubest;

/**
 * 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
 *
 * 插入排序 算法的步骤:
 *
 * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 * 重复直到所有输入数据插入完为止。
 * 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
 *
 * 对链表进行插入排序。
 *
 *
 *
 *  
 *
 * 示例 1：[图片] img/0147_1.jpg
 *
 *
 *
 * 输入: head = [4,2,1,3]
 * 输出: [1,2,3,4]
 *
 * 示例 2：[图片] img/0147_2.jpg
 *
 *
 *
 * 输入: head = [-1,5,3,4,0]
 * 输出: [-1,0,3,4,5]
 *  
 *
 * 提示：
 *
 * 列表中的节点数在 [1, 5000]范围内
 * -5000 <= Node.val <= 5000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/insertion-sort-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2022/3/28 17:46
 */
public class P0147 {

    public static void main(String[] args) {
        ListNode head = new ListNode(-1, new ListNode(5, new ListNode(3, new ListNode(4, new ListNode(0)))));
        new Solution147().insertionSortList(head);
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution147 {

    public ListNode insertionSortList(ListNode head) {
        ListNode cur = head.next, next, guard = new ListNode(-5001, new ListNode(head.val));
        while (null != cur) {
            next = cur.next;
            insertionSortList(cur, guard);
            cur = next;
        }
        return guard.next;
    }

    private void insertionSortList(ListNode curNode, ListNode head) {
        ListNode pre = head, cur = head.next;
        while (null != cur) {
            if (curNode.val >= pre.val && curNode.val <= cur.val) {
                pre.next = curNode;
                curNode.next = cur;
                return;
            }
            pre = cur;
            cur = cur.next;
        }
        pre.next = curNode;
        curNode.next = null;
    }
}
